/**
 * 对于某些非负整数 k ，如果交换 s1 中两个字母的位置恰好 k 次，能够使结果字符串等于 s2 ，则认为字符串 s1 和 s2 的 相似度为 k 。
 *
 * 给你两个字母异位词 s1 和 s2 ，返回 s1 和 s2 的相似度 k 的最小值。
 *
 * 链接：https://leetcode.cn/problems/k-similar-strings
 * 题解：https://leetcode.cn/problems/k-similar-strings/solution/zhua-wa-mou-si-by-muse-77-b79a/
 */

class KSimilarity {
    /**
     * 法二：回溯
     */
    int count=Integer.MAX_VALUE;
    public int kSimilarity(String s1, String s2) {
        kSimilarity(s1.toCharArray(),s2,0,0,s1.length());
        return count;
    }
    public void kSimilarity(char[] s1,String s2,int sum,int i,int len) {
        if(sum>=count) {
            return ;
        }
        if(i==len-1) {
            count=Math.min(sum,count);
            return;
        }
        for(int j=i;j<len;j++) {
            if(s1[j]!=s2.charAt(j)) {
                for(int k=j+1;k<len;k++) {
                    if(s1[k]==s2.charAt(j)&&s1[k]!=s2.charAt(k)) {
                        swap(s1,k,j);
                        kSimilarity(s1,s2,sum+1,j+1,len);
                        swap(s1,k,j);
                        //如果字符串s1，s2当前要交换的j,k值相等，说明，一次交换两个位置匹配，那么这就是最好的交换，直接跳出
                        if(s1[j]==s2.charAt(k)) {//剪枝
                            break;
                        }
                    }
                }
                //已经将每条路径都访问过了，直接返回
                return;
            }

        }
        count=Math.min(count,sum);

    }
    public void swap(char[] s1,int k,int j) {
        char tmp=s1[k];
        s1[k]=s1[j];
        s1[j]=tmp;
    }
    /**
     * 法二：广度优先遍历
     * @param s1
     * @param s2
     * @return
     */
    public int kSimilarity2(String s1, String s2) {
        Queue<Pair<String,Integer>> qu=new LinkedList<>();
        Set<String> vist=new HashSet<>();
        int step=0;
        qu.offer(new Pair<>(s1,0));
        int n=s1.length();
        vist.add(s1);
        while(!qu.isEmpty()) {
           int size=qu.size();
           for(int i=0;i<size;i++) {
               Pair<String,Integer> pair=qu.poll();
               String cur=pair.getKey();
               int pos=pair.getValue();
               if(cur.equals(s2)) {
                   return step;
               }
               while(pos<n&&cur.charAt(pos)==s2.charAt(pos)) {
                   pos++;
               }
               for(int j=pos+1;j<n;j++) {
                   if(s2.charAt(j)==cur.charAt(j)) {
                       continue;
                   }
                   if(s2.charAt(pos)==cur.charAt(j)) {
                       String next=swap(cur,pos,j);
                       if(!vist.contains(next)) {
                           vist.add(next);
                           qu.offer(new Pair<String,Integer>(next,pos+1));
                       }
                   }
               }
           }
           step++;
        }
        return step;
    }
    public String swap(String cur,int i,int j) {
        char[] arr=cur.toCharArray();
        char c=arr[i];
        arr[i]=arr[j];
        arr[j]=c;
        return new String(arr);
    }
}